package com.leetcode.algorithm.y22.m06;

/**
 * 5. 最长回文子串
 * 
 * https://leetcode.cn/problems/longest-palindromic-substring/
 * 
 * @author jie.deng
 *
 */
class Question0005Solution01 {
	
	public String longestPalindrome(String s) {
		int len = s.length();
		// dp[i][j]表示s.substring(i, j+1)是否是回文串
		boolean[][] dp = new boolean[len][len];
		// dp状态初始化
		for (int i = 0; i < len; i++) {
			// 单字符初始化
			dp[i][i] = true;
		}
		// 最后一行
		// dp[len - 1][len - 1] = true;

		String retStr = s.substring(0, 1);
		int maxLen = 1;

		// 依赖方向右上依赖左下：dp[i][j] = dp[i+1][j-1] && s.charAt(i) == s.charAt(j)
		// 计算方向左下到右上
		for (int i = len - 2; i >= 0; i--) {
			for (int j = i + 1; j < dp.length; j++) {
				if (s.charAt(i) == s.charAt(j)) {
					if (j - i == 1 || dp[i + 1][j - 1]) {
						// 双字符并且回文的情况
						// 多字符，则减去头尾相同字符后，看剩余字符是否回文
						dp[i][j] = true;
						if (j - i + 1 > maxLen) {
							maxLen = j - i + 1;
							retStr = s.substring(i, j + 1);
						}
					}
				}
			}
		}
		return retStr;
	}
    
}